package leetcode_2101_2200;

import java.util.TreeMap;

public class LeeCode_2111 {
    public static void main(String[] args) {
        System.out.println(kIncreasing(new int[]{12,6,12,6,14,2,13,17,3,8,11,7,4,11,18,8,8,3}, 1));
//        System.out.println(kIncreasing(new int[]{5, 4, 3, 2, 1}, 1));
//        System.out.println(kIncreasing(new int[]{4,1,5,2,6,2}, 2));
//        System.out.println(kIncreasing(new int[]{4,1,5,2,6,2}, 3));
    }
    private static int kIncreasing(int[] arr, int k) {
        int n = arr.length, ans = n;
        if (n == k)
            return 0;
        for (int i = 0; i < k; i++) {
            int[] nums =  new int[n / k + 5];
            nums[0] = arr[i];
            int p = 0;
            for (int j = i + k; j < n; j += k){
                if (arr[j] >= nums[p]){
                    p++;
                    nums[p] = arr[j];
                }else {
                    int l = 0, r = p;
                    while (l < r){
                        int m = (l + r) >> 1;
                        if (nums[m] > arr[j]){
                            r = m;
                        }else {
                            l = m + 1;
                        }
                    }
                    nums[l] = arr[j];
                }
            }
            ans -= p + 1;
        }
        return ans;
    }
}